package graph;

import java.util.Iterator;
import java.util.Vector;

/**
 * O(v+e),tested
 * 
 * @author yinzichen
 * 
 */
public class EulerTour {
	Vector<Vector<Integer>> adj;
	Vector<Integer> ans;
	int idx;

	public Vector<Integer> eulerTourDirectedRecursive(int s,
			Vector<Vector<Integer>> directedGraph) {
		adj = directedGraph;
		idx = 0;
		ans = new Vector<Integer>();
		dfs(s);
		return ans;
	}

	private void dfs(int u) {
		int size = 0;
		while ((size = adj.get(u).size()) > 0) {
			int v = adj.get(u).remove(size - 1);
			dfs(v);
		}
		ans.add(u);
	}

	public Vector<Integer> eulerTourDirected(int s, Vector<Vector<Integer>> adj) {
		int i, j;
		int n = adj.size();
		int edgenum = 0;
		Vector<Integer> ans = new Vector<Integer>();
		int[] stack;
		int top = -1;
		for (i = 0; i < n; ++i)
			edgenum += adj.get(i).size();
		stack = new int[edgenum + 1];
		stack[++top] = s;
		Vector<Iterator<Integer>> it = new Vector<Iterator<Integer>>();
		for (i = 0; i < n; i++)
			it.add(adj.get(i).iterator());
		while (top != -1) {
			i = stack[top];
			if (!it.get(i).hasNext())
				ans.add(stack[top--]);
			else {
				j = it.get(i).next();
				stack[++top] = j;
			}
		}
		return ans;
	}
}